package 算法.字符串.单词查找树;

import com.sun.jndi.url.dns.dnsURLContext;

import sun.net.www.content.audio.x_aiff;
import util.LogUtils;



/**
 * 【单词查找树：三向】
 * 
 * @Date 2017-09-08 22：29
 * @author Administrator
 * @version 
 */
public class TST {
	private Node root;
	private static class Node {
		public char ch;
		public int  val;			//代表：单词结尾
		public Node left, mid, right;
		public Node(char ch) {
			this.ch = ch;
		}
		@Override
		public String toString() {
			return "Node [ch=" + ch + ", val=" + val + ", left=" + left
					+ ", mid=" + mid + ", right=" + right + "]";
		}
	}
	
	/**
	 * get()：
	 * @param key
	 * @return
	 */
	public Integer get(String key) {
		Node node = get(root, key, 0);
		if (node == null)	return null;
		return node.val;
	}
	
	public Node get(Node x, String key, int offset) {
		if (x == null) 						return null;
		char c = key.charAt(offset);
		if 		(c < x.ch)					return get(x.left, 	key, offset);
		else if (c > x.ch)					return get(x.right, key, offset);
		else if (offset < key.length()-1)	return get(x.mid, 	key, offset+1);
		return x;
	}
	
	/**
	 * put()：
	 * @param key
	 * @param val
	 */
	public void put(String key, int val) {
		root = put(root, key, val, 0);
		traverse(root);
	}
	
    private Node put(Node x, String key, int val, int offset) {
    	char c = key.charAt(offset);
    	if (x == null)						x = new Node(c);
    	if 		(c < x.ch)					x.left  = put(x.left,  key, val, offset);	//offset不变
    	else if (c > x.ch)					x.right = put(x.right, key, val, offset);	//offset不变
    	else if (offset < key.length()-1)	x.mid = put(x.mid, key, val, offset+1);		//offset加1
    	else x.val = val;
    	return x;
    }

	
	
	/**
	 * 前序遍历
	 */
	public void traverse(Node root) {
		if (root == null) return;
		LogUtils.println("TST 前序遍历", root);
		traverse(root.left);
		traverse(root.mid);
		traverse(root.right);
	}
	
	public static void main(String[] args) {
		TST tst = new TST();
		tst.put("are",    12);
		tst.put("by",      4);
		tst.put("sea",    14);
		tst.put("sells",  11);
		tst.put("shells", 15);
		tst.put("shore",   7);
		tst.put("surely", 13);
		LogUtils.println("GET>>>", tst.get("are"));
		LogUtils.println("GET>>>", tst.get("sells"));
		LogUtils.println("GET>>>", tst.get("shore"));
	}
}
